package ca.qc.bdeb.jeuxdesboites.model;

import ca.qc.bdeb.jeuxdesboites.commun.Coup;
import ca.qc.bdeb.utilitaires.Direction;
import ca.qc.bdeb.jeuxdesboites.commun.IDJoueurs;
import java.awt.Point;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *
 * @author Eric Wenaas <eric.wenaas@bdeb.qc.ca>
 */
public class MiniMax implements AnalyseAI {

    /* Analyser position appelle minimax et retourne le vecteur de coups candidats
     */
    // TODO: Il n'y a pas d'Alpha-Beta pruning ni de cache de positions déjà
    //       analysées dans MiniMax
    @Override
    public ArrayList<Coup> analyserPosition(TableauJeu position) {
        TableauJeu copiePosition = (TableauJeu) position.clone();
        ArrayList<Coup> reponse = new ArrayList<>();
        Coup coupFacile = trouverCoupFacile(copiePosition);
        if (coupFacile != null) {
            reponse.add(coupFacile);
        } else {
            GroupesVulnerable groupes = new GroupesVulnerable(position);
            if (compterCasesSecuritaires(copiePosition, groupes) == 0) {
                Coup donPetitGroupe = donnerGroupeMinimum(copiePosition, groupes);
                reponse.add(donPetitGroupe);
            } else {
                
                // On part MiniMax
                ArrayList<Coup> coupsCandidats = copiePosition.determinerCandidats();
                int horizonMaximal = determinerProfondeurAnalyse(copiePosition, coupsCandidats, groupes);
                int evaluationInitiale = 0x80000000;
                int meilleureEvaluation = evaluationInitiale;
                for (Coup coupAnalyse : coupsCandidats) {
                    int evaluationCourante;
                    copiePosition.jouerCoup(IDJoueurs.JOUEUR_ARTIFICIEL, coupAnalyse);
                    boolean continuer = copiePosition.isBoiteFerme(coupAnalyse.positionX, coupAnalyse.positionY);
                    if (continuer) {
                        evaluationCourante = max(copiePosition, horizonMaximal);
                    } else {
                        evaluationCourante = min(copiePosition, horizonMaximal);
                    }
                    if (evaluationCourante == meilleureEvaluation) {
                        reponse.add(coupAnalyse);
                    } else if (evaluationCourante > meilleureEvaluation) {
                        reponse.clear();
                        reponse.add(coupAnalyse);
                        meilleureEvaluation = evaluationCourante;
                    }
                    copiePosition.dejouerCoup(coupAnalyse);
                }
            }
        }
        return reponse;
    }

    int min(TableauJeu tableau, int profondeurRestante) {
        int reponse = 0x7fffffff;
        boolean encore;
        GroupesVulnerable groupesVulnerables = new GroupesVulnerable(tableau);
        if (compterCasesSecuritaires(tableau, groupesVulnerables) == 0 ||
            tableau.isComplet() || profondeurRestante == 0) {
            reponse = evaluerPosition(tableau, IDJoueurs.JOUEUR_HUMAIN);
        } else {
	    Coup coupFacile = trouverCoupFacile(tableau);
	    if (coupFacile != null) {
		tableau.jouerCoup(IDJoueurs.JOUEUR_HUMAIN, coupFacile);
		reponse =  min(tableau, profondeurRestante);
		tableau.dejouerCoup(coupFacile);
	    } else {

		// TODO: Faire en sorte que la liste de coups calculee au niveau superieur
		//       soit réutilisée
		ArrayList<Coup> coupsCandidats = tableau.determinerCandidats();
		for (Coup unCoup : coupsCandidats) {
		    tableau.jouerCoup(IDJoueurs.JOUEUR_HUMAIN, unCoup);
		    encore = tableau.isBoiteFerme(unCoup.positionX, unCoup.positionY);
		    
		    if (encore) {
			reponse = min(tableau, profondeurRestante);
		    } else {
			int candidat = max(tableau, profondeurRestante - 1);
			if (candidat < reponse) {
			    reponse = candidat;
			}
		    }
		    tableau.dejouerCoup(unCoup);
		}
	    }
        }
        return reponse;
    }

    int max(TableauJeu tableau, int profondeurRestante) {
        int reponse = 0x80000000;
        boolean encore;

       GroupesVulnerable groupesVulnerables = new GroupesVulnerable(tableau);
        
        if (compterCasesSecuritaires(tableau, groupesVulnerables) == 0 ||
            tableau.isComplet() || profondeurRestante == 0) {
            reponse = evaluerPosition(tableau, IDJoueurs.JOUEUR_ARTIFICIEL);
        } else {
	    Coup coupFacile = trouverCoupFacile(tableau);
	    if (coupFacile != null) {
		tableau.jouerCoup(IDJoueurs.JOUEUR_ARTIFICIEL, coupFacile);
		reponse =  max(tableau, profondeurRestante);
		tableau.dejouerCoup(coupFacile);
	    } else {

		ArrayList<Coup> coupsCandidats = tableau.determinerCandidats();
		for (Coup unCoup : coupsCandidats) {
		    tableau.jouerCoup(IDJoueurs.JOUEUR_ARTIFICIEL, unCoup);
		    encore = tableau.isBoiteFerme(unCoup.positionX, unCoup.positionY);
		    
		    if (encore) {
			reponse = max(tableau, profondeurRestante);
		    } else {
			int candidat = min(tableau, profondeurRestante - 1);
			if (candidat > reponse) {
			    reponse = candidat;
			}
		    }
		    tableau.dejouerCoup(unCoup);
		}
	    }
        }
        return reponse;
    }

    private int evaluerPosition(TableauJeu tableau, IDJoueurs joueurActif) {
        int reponse = 0;
        int pointsAI = tableau.getNombrePoints(IDJoueurs.JOUEUR_ARTIFICIEL);
        int pointsAdversaire = tableau.getNombrePoints(IDJoueurs.JOUEUR_HUMAIN);
        
        GroupesVulnerable groupesVulnerables = new GroupesVulnerable(tableau);
        int casesSecuritaires = compterCasesSecuritaires(tableau, groupesVulnerables); 
    
        if (! tableau.isComplet() && casesSecuritaires == 0) {
            GroupesVulnerable groupes = new GroupesVulnerable(tableau);
            IDJoueurs joueurConsidere = joueurActif;
            while (! groupes.isEmpty()) {
                List<Point> groupe = groupes.obtenirPlusPetit();
                int tailleGroupe = groupe.size();
                groupes.remove(groupe);
                if (joueurConsidere.equals(IDJoueurs.JOUEUR_ARTIFICIEL)) {
                    pointsAI += tailleGroupe;
                    joueurConsidere = IDJoueurs.JOUEUR_HUMAIN;
                } else {
                    pointsAdversaire += tailleGroupe;
                    joueurConsidere = IDJoueurs.JOUEUR_ARTIFICIEL;
                }
            }
        }
        reponse = pointsAI - pointsAdversaire;

        if (tableau.isComplet() || casesSecuritaires == 0) {
            // Si la partie est terminee, alors il faut donner plus d'importance a
            // l'evaluation, car elle prime sur des evaluations partielles incertaines.
            reponse = reponse * 1000;
        }
        return reponse;
    }

    private int compterCasesSecuritaires(TableauJeu tableau, 
                                         GroupesVulnerable groupes) {
        Set<Point> ensembleCaseslibres = new HashSet<>();
	int largeur = tableau.getLargeur();
	int hauteur = tableau.getHauteur();

	for (int x=0; x<largeur; x++) {
	    for (int y=0; y<hauteur; y++) {
                if (! tableau.isBoiteFerme(x, y)) {
                    ensembleCaseslibres.add(new Point(x,y));
                }
	    }
	}
        for (List<Point> aList : groupes) {
            for (Point p : aList) {
                ensembleCaseslibres.remove(p);
            }
        }
	return ensembleCaseslibres.size();
    }

    // TODO: La détermination de la profondeur d'analyse est en expérimentation
    private int determinerProfondeurAnalyse(TableauJeu tableau, 
                                            List<Coup> coupsCandidats,
                                            GroupesVulnerable groupes)  {
	int profondeur;
	int nbCasesSecuritaires = compterCasesSecuritaires(tableau, groupes);
        int nbCoupsPossibles =  (tableau.getHauteur() + 1) * tableau.getLargeur() +
                                (tableau.getLargeur() + 1) * tableau.getHauteur();
        double rapportSecurite = coupsCandidats.size() / (double) nbCoupsPossibles; 
	if (nbCasesSecuritaires == 0) {
	    profondeur = groupes.size();
        } else if (rapportSecurite >= 0.70) {
            profondeur = 1;
        } else if (rapportSecurite >= 0.40)  {
            profondeur = 2;
        } else if (rapportSecurite >= 0.20) {
            profondeur = 3;
        } else {
            profondeur = 4;
        }
	return profondeur;
    }
    
    /*
     * Un coup facile est une case qui permet de fermer une boîte.
     */
    private Coup trouverCoupFacile(TableauJeu tableau) {
        Coup coupFacile = null; 
        ArrayList<Coup> coupsCandidats = tableau.determinerCandidats();
        for (Coup unCoup : coupsCandidats) {
            boolean boiteFermee = tableau.jouerCoup(IDJoueurs.JOUEUR_ARTIFICIEL, unCoup);
            if (boiteFermee) {
                coupFacile = unCoup;
                tableau.dejouerCoup(unCoup);
                break;
            }
            tableau.dejouerCoup(unCoup);
        }
        return coupFacile;
    }
    
    /*
     * Donne à l'adversaire le groupe le moins payant
     */
    private Coup donnerGroupeMinimum(TableauJeu tableau,
                                     GroupesVulnerable groupes) {
        Coup reponse = null;
        List<Point> listeCible = groupes.obtenirPlusPetit();
        Point coordonneesChoisies = listeCible.get(0);
        Boite boiteChoisie = tableau.getBoite(coordonneesChoisies.x, 
                                              coordonneesChoisies.y);
        for (Direction d : Direction.values()) {
            if (! boiteChoisie.isFermeeDirection(d)) {
                reponse = new Coup(coordonneesChoisies.x, coordonneesChoisies.y,
                                   d);
                break;
            }
        }
        return reponse;
    }
}
